//二叉树数据结构TreeNode可用来表示单向链表（其中left置空，right为下一个链表节点）。实现一个方法，把二叉搜索树转换为单向链表，要求依然符合二叉
//搜索树的性质，转换操作应是原址的，也就是在原始的二叉搜索树上直接修改。 
//
// 返回转换后的单向链表的头节点。 
//
// 注意：本题相对原题稍作改动 
//
// 
//
// 示例： 
//
// 输入： [4,2,5,1,3,null,6,0]
//输出： [0,null,1,null,2,null,3,null,4,null,5,null,6]
// 
//
// 提示： 
//
// 
// 节点数量不会超过 100000。 
// 
//
// Related Topics 栈 树 深度优先搜索 二叉搜索树 链表 二叉树 👍 152 👎 0


package LeetCode.editor.cn;


/**
 * @author ldltd
 * @date 2025-09-16 17:01:29
 * @description 面试题 17.12.BiNode
 
 */
 
public class BinodeLcci {
    public static void main(String[] args) {
    //测试代码
    BinodeLcci fun = new BinodeLcci();
    Solution solution= fun.new Solution();
    
    }

//leetcode submit region begin(Prohibit modification and deletion)

 //  Definition for a binary tree node.
  public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
  }
class Solution {
    public TreeNode convertBiNode(TreeNode root) {
        if (root == null) {
            return null;
        }
        TreeNode dummy = new TreeNode(-1); // 创建一个哑节点，方便返回结果
        TreeNode[] prev = new TreeNode[1]; // 用于记录前一个节点
        prev[0] = dummy; // 初始化前一个节点为哑节点

        inOrder(root, prev);

        return dummy.right; // 返回链表的头节点
    }
    private void inOrder(TreeNode node, TreeNode[] prev) {
        if (node == null) {
            return;
        }
        // 递归左子树
        inOrder(node.left, prev);

        // 处理当前节点
        prev[0].right = node; // 将前一个节点的右指针指向当前节点
        node.left = null; // 将当前节点的左指针置空
        prev[0] = node; // 更新前一个节点为当前节点

        // 递归右子树
        inOrder(node.right, prev);
    }

    // 迭代法
    public TreeNode convertBiNode2(TreeNode root) {
        if (root == null) {
            return null;
        }
        TreeNode dummy = new TreeNode(-1); // 创建一个哑节点，方便返回结果
        TreeNode prev = dummy; // 用于记录前一个节点
        java.util.Stack<TreeNode> stack = new java.util.Stack<>();
        TreeNode current = root;

        while (current != null || !stack.isEmpty()) {
            // 遍历左子树
            while (current != null) {
                stack.push(current);
                current = current.left;
            }
            // 处理当前节点
            current = stack.pop();
            prev.right = current; // 将前一个节点的右指针指向当前节点
            current.left = null; // 将当前节点的左指针置空
            prev = current; // 更新前一个节点为当前节点

            // 遍历右子树
            current = current.right;
        }

        return dummy.right; // 返回链表的头节点
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}
